#define _CRT_SECURE_NO_WARNINGS 1

//typedef int STDataType;
//typedef struct Stack
//{
//	STDataType* a;
//	int top;
//	int capacity;
//}ST;
//
//void StackInit(ST* ps);
//void StackDestroy(ST* ps);
//void StackPush(ST* ps, STDataType x);
//void StackPop(ST* ps);
//
//STDataType StackTop(ST* ps);
//bool StackEmpty(ST* ps);
//int StackSize(ST* ps);
//
//void StackInit(ST* ps)
//{
//	assert(ps);
//	ps->a = NULL;
//	ps->capacity = ps->top = 0;
//}
//
//void StackDestroy(ST* ps)
//{
//	assert(ps);
//	free(ps->a);
//	ps->a = NULL;
//	ps->capacity = ps->top = 0;
//}
//
//void StackPush(ST* ps, STDataType x)
//{
//	assert(ps);
//	if (ps->capacity == ps->top)
//	{
//		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
//		if (tmp == NULL)
//		{
//			perror("relloc fail");
//			exit(-1);
//		}
//		ps->a = tmp;
//		ps->capacity = newcapacity;
//	}
//	ps->a[ps->top] = x;
//	ps->top++;
//}
//
//void StackPop(ST* ps)
//{
//	assert(ps);
//	assert(!StackEmpty(ps));
//	ps->top--;
//}
//
//STDataType StackTop(ST* ps)
//{
//	assert(ps);
//	assert(!StackEmpty(ps));
//	return ps->a[ps->top - 1];
//}
//
//bool StackEmpty(ST* ps)
//{
//	assert(ps);
//	return ps->top == 0;
//}
//
//int StackSize(ST* ps)
//{
//	assert(ps);
//	return ps->top;
//}
//
//
//typedef struct
//{
//	ST dataST;
//	ST minST;
//} MinStack;
//
//MinStack* minStackCreate()
//{
//	MinStack* s = (MinStack*)malloc(sizeof(MinStack));
//	StackInit(&s->dataST);
//	StackInit(&s->minST);
//	return s;
//}
//
//void minStackPush(MinStack* obj, int x)
//{
//	if (StackEmpty(&obj->minST))
//	{
//		StackPush(&obj->minST, x);
//	}
//	else
//	{
//		if (x <= StackTop(&obj->minST))
//		{
//			StackPush(&obj->minST, x);
//		}
//		else
//		{
//			int top = StackTop(&obj->minST);
//			StackPush(&obj->minST, top);
//		}
//	}
//	StackPush(&obj->dataST, x);
//}
//
//void minStackPop(MinStack* obj)
//{
//	if (!StackEmpty(&obj->dataST))
//	{
//		StackPop(&obj->minST);
//		StackPop(&obj->dataST);
//	}
//}
//
//int minStackTop(MinStack* obj)
//{
//	return StackTop(&obj->dataST);
//}
//
//int minStackMin(MinStack* obj)
//{
//	return StackTop(&obj->minST);
//}
//
//void minStackFree(MinStack* obj)
//{
//	StackDestroy(&obj->dataST);
//	StackDestroy(&obj->minST);
//	free(obj);
//}

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}


typedef struct
{
	ST dataST;
	ST minST;
} MinStack;

MinStack* minStackCreate()
{
	MinStack* s = (MinStack*)malloc(sizeof(MinStack));
	StackInit(&s->dataST);
	StackInit(&s->minST);
	return s;
}

void minStackPush(MinStack* obj, int x)
{
	if (StackEmpty(&obj->minST))
	{
		StackPush(&obj->minST, x);
	}
	else
	{
		if (x <= StackTop(&obj->minST))
		{
			StackPush(&obj->minST, x);
		}
	}
	StackPush(&obj->dataST, x);
}

void minStackPop(MinStack* obj)
{
	if (!StackEmpty(&obj->dataST))
	{
		if (StackTop(&obj->dataST) == StackTop(&obj->minST))
		{
			StackPop(&obj->minST);
		}
		StackPop(&obj->dataST);
	}
}

int minStackTop(MinStack* obj)
{
	return StackTop(&obj->dataST);
}

int minStackMin(MinStack* obj)
{
	return StackTop(&obj->minST);
}

void minStackFree(MinStack* obj)
{
	StackDestroy(&obj->dataST);
	StackDestroy(&obj->minST);
	free(obj);
}